public class Code1 {
    // 最大子数组和

    public int maxSubArray(int[] nums) {
        // 创建 dp 表
        // 初始化
        // 填表
        // 返回结果

        // 这里创建 dp 表我们使用的是创建虚拟节点的方式，长度就是数组长度+1
        int n = nums.length;
        int[] dp = new int[n + 1];

        // 要了解 dp[i] 表示的是以 i 元素为结尾时 所有子数组中 的最大和
        // 对于初始化，这里的虚拟节点不设值默认就为 0 即可

        // 填表
        // 这里我们可以将数组中的信息分为两部分
        // 第一部分：只关注当前 nums[i] 位置的信息
        // 第二部分：关注 nums[i] 结尾之前数组连续下的最大值
        //          此时，dp[i-1] 所表示的正是当前数组值之前数据和的最大值
        int ret = Integer.MIN_VALUE;
        for(int i = 1; i <= n; i++){
            dp[i] = Math.max(nums[i - 1], nums[i - 1] + dp[i - 1]);
            // 一边填表一边找最大值
            ret = Math.max(ret,dp[i]);
        }
        // 确定返回值
        // 这里的返回值是 dp 表中的最大值
        return ret;
    }
}
